
\section{Descripción del Problema}
Dado un tablero de ajedrez de $n * n$ y $k$ caballos ubicados aleatoreamente 
en el tablero, pudiendo haber más de un caballo por casilla, se debe encontrar
la casilla del tablero hacia la cual se puede mover todos los caballos
de manera de reducir la cantidad de saltos que se deben hacer 
sumando los saltos de todos los caballos ubicados en el tablero, en 
su recorrido hacia esta casilla. También se debe tener en cuenta
que los caballos se mueven de la manera que lo hacen en un juego de ajedez y 
que es posible que 2 caballos pisen la misma casilla. \\
Planteado el  problema, adicionalmente  se debe resolver  en  complejidad no peor 
a $O(k*n^2)$.


\subsection{Ejemplo}
Dado un tablero de $5 * 5$ y 3 caballos. 
\begin{table}[h]
\begin{tabular}{l|l|l|l|l|l|}
 & 0 & 1  &  2 & 3   & 4  \\ \hline
0 & X &   &   &    &   \\ \hline
1   & &   &   &    &   \\ \hline
2   & &   & X &    &   \\ \hline
 3  & &   &   &  X &   \\ \hline
 4  & &   &   &    &   \\ \hline
\end{tabular}
\end{table}

Numerando la tabla de 0 a 4 podemos ver que la posicion
$(0,0)$ en el margen superior izquierdo tiene un caballo asi como
las posiciones $(2,2)$ y (3,3). \\
Ahora armando una matriz con la cantidad de saltos 
que requiere cada casilla, si se ubicaran los 3 caballos en 
esta podemos ver cuales son las que minimizan los saltos totales.\\
\begin{table}[h]
\begin{tabular}{l|l|l|l|l|l|}
& 0 & 1  &  2 & 3   & 4  \\ \hline
0 & (0,4,2)=6 & (4,1,3)=8  & (2,2,2)=6 & (3,1,3)=7 & (2,4,2)=8 \\ \hline
1 & (3,1,3)=7 & (4,2,4)=10 & (1,3,1)=5 & (2,2,2)=6 & (3,1,1)=5 \\ \hline
2 & (2,2,2)=6 & (1,3,1)=5  & (4,0,2)=6 & (3,3,3)=9 & (4,2,2)=8 \\ \hline
3 & (3,1,3)=7 & (2,2,2)=6  & (3,3,3)=9 & (2,2,0)=4 & (3,1,3)=7 \\ \hline
4 & (2,4,2)=8 & (3,1,1)=5  & (2,2,2)=6 & (3,1,3)=7 & (0,4,2)=6 \\ \hline
\end{tabular}
\end{table}\\
En esta tabla calculada a mano se puede ver, que el casillero
que minimiza los saltos en este caso es el $(3,3)$. Si movieramos
todos los caballos a este casillero solo hariamos 4 saltos en total, 2
para el caballo en la posicion $(0,0)$ y 2 para el caballo en la posicion $(2,2)$

\section{Idea General de la Resolución}
Para la resolución del problema se pensó en Programación Dinámica (Dado un problema grande, subdividirlo en problemas más pequeños). En este sentido nos centramos en el problema de buscar la mínima cantidad de movimientos de un caballo desde una casilla inicial $C{i}$ hasta una casilla final $C{f}$. Pensándolo recursivamente se tiene que: para saber la mínima cantidad de saltos para llegar a la casilla $C_f$, necesito saber la mínima cantidad de saltos para llegar hasta casillas anteriores.\\
\\
\textbf{Definición} Llamamos \textbf{Vecinas($C_i$)} al conjunto de casillas vecinas a $C_i$, entendiendo como "casillas vecinas" a las que estan a distancia de un solo salto a $C_i$. Como ejemplo tomo el gráfico de la sección anterior y tomando como $C = (2,2)$ sabemos que sus casillas vecinas son $Vecinas(C) = \{(0,1),(0,3),(1,0),(1,4),(3,0),(3,4),(4,1),(4,3)\}$
Sabiendo esto se puede pensar de manera recursiva en la siguiente función:

\begin{equation}
     minSaltos(Cf) = \left\{
	       \begin{array}{ll}
		 0      & \mathrm{si\ } Cf = Ci \\
		 \\
		 (minimo \left\{
				\begin{array}{ll}
				minSaltos(C1)\\
				minSaltos(C2)\\
				....\\
				....\\
				minSaltos(C8)\\
				\end{array}
				\right. )  + 1 &  \mathrm{sino\ } \\
		    \end{array}
	     \right.
 \end{equation}
 Donde $C_f$ es la casilla final (a la que hay que llegar con la menos cantidad de saltos), $C_i$ la casilla inicial y Vecinos($C_f$) = $\{C1,C2,C3,C4,C5,C6,C7,C8\}$ Pero para saber la minima cantidad de saltos hasta la casilla $C_f$ se necesita saber la minima cantidad de saltos de sus vecinos, o por lo menos del vecino cuya mínima cantidad de saltos sea menor.
 Para pensarlo un poco mejor se define lo siguiente:\\
 \\
\textbf{Definición $C_{k,(x,y)}$ }= Conjunto de casillas cuya mínima cantidad de saltos desde la casilla $(x,y)$ es igual a $k$ .\\
 El siguiente es un ejemplo de un tablero de 5 x 5
 
 \begin{table}[h]
\begin{tabular}{l|l|l|l|l|l|}
  & 0 & 1  &  2 & 3   & 4  \\ \hline
0 &   &  X &    &  X  &   \\ \hline
1 & X &    &    &     & X \\ \hline
2 &	  &    &$C_i$&     &   \\ \hline
3 & X &    &    &     & X \\ \hline
4 &   &  X &    &  X  &   \\ \hline
\end{tabular}
\end{table}

\begin{itemize}
\item Si la casilla inicial de un caballo es la (2,2) como muestra la imágen entonces $C_{0(2,2)} = \{(2,2)\}$ ya que solo (2,2) es la casilla a la que se puede llegar con un movimiento minimo de cero.
\item Luego $C_{1(2,2)}$ esta formada por todas las casillas marcadas con un "X", y son todas vecinas de $C_i$.
\item Se puede llegar a pensar que $C_{2(2,2)}$ esta formada por todas las casillas vecinas a cada elemento de $C_{1(2,2)}$ pero no es así. Por ejemplo la casilla $(0,1)$ pertenece a $C_{1(2,2)}$, y $(2,2)$ pertenece a $Vecinas((0,1))$ sin embargo $(2,2)$ pertenece a  $C_{0(2,2)}$ y no a $C_{2(2,2)}$, solo puede pertenecer a uno y solo un conjunto. 
\end{itemize}

Volviendo a la función recursiva $minSaltos$ se puede llegar a pensar que dada una casilla final $C_f$, dicha casilla ya pertenece a algún $C_{k(C_i)}$ con $C_i$ como casilla inicial, entonces nos interesa averiguar el valor de $k$ y seguro alguno de sus vecinos va a tener que perteneces a $C_{k-1(C_i)}$, seguro porque para llegar con $k$ movimientos a $C_f$ necesita antes pasar por alguna casilla que pertenece a $Vecinos(C_f)$ (eso si $C_f$ no es igual a $C_i$).\\
Pensándolo de esa manera podemos tomar el enfoque \textit{bottom-up} para la programación dinámica (Todos los problemas que puedan ser necesarios se resuelven de antemano y después se usan para resolver las soluciones a problemas mayores.)\\
\\
La idea es ir llenando a partir de la posición inicial cada casilla con $k$ de acuerdo al conjunto $C_{k(C_i)}$ al que pertenezca con $k$ número no negativo y $C_i$ casilla inicial, de este modo no solo encontramos el $minSaltos$ para una casilla $C_f$ en particular sino para cualquier casilla dl tablero dada una casilla inicial $C_i$.
Para lograrlo se necesita pensar el algoritmo de la siguiente manera:
\begin{itemize}
\item Se define el conjunto $C_{0(C_i)} = \{C_i\}$ asignandole el valor 0 a la casilla $C_i$.
\item Una vez definido el conjunto $C_{k(C_i)}$ se define el conjunto $C_{k+1(C_i)}$ como todos las casillas $C$ tal que sean vecinos de algun elemento que pertenezca a $C_{k(C_i)}$ y $C$ no pertenezca a ningun conjunto $C_{t(C_i)}$ con $ 0 \le t \le k$ . 
\end{itemize}

%Para la resolucion se busco la manera de reutilizar calculos para poder 
%llegar a la complejidad. Mirando el ejemplo anterior se penso primero 
%en el caso en el que el tablero no tiene bordes, para despues 
%ver estos casos tambien. \\
%En caso de no tener bordes el tablero, si se como mover un caballo
%desde la posicion $(i_0,j_0)$ a la posicion $(i_1,j_1)$ con la menor 
%cantidad de saltos. Entonces puedo transladar este conocimiento a cualquier punto
%del tablero. La forma en que reutilizo ese resultado es
%tomando el valor absoluto de la diferencia entre coordenadas. 
%Sabiendo la cantidad minima de saltos  desde $(i_0,j_0)$
%a $(i_1,j_1)$, tomo como clave el valor $(abs(i_1-i_0),abs(j_1,j_0))$. 
%Con esa clave puedo armar una tabla en la que tengo 
%$(abs(x-w),abs(y-z))$ $\rightarrow$ $C$ con $C$ la menor cantidad de saltos y 
%$(x,y)$ , $(w,z)$ dos puntos cualesquiera en el tablero.
%La forma en la que se va completando esta tabla es preguntando 
%para un caballo cualquiera, cuantos saltos debe hacer para llegar a 
%otro casillero. En caso de ser vecino, (que se puede alcanzar 
%con un solo salto de caballo), sera 1 solo salto. Entonces 
%se guardara $(abs(x-w),abs(y-z))$ $\rightarrow$ $1$. En caso de
%no ser vecino, la cantidad de saltos sera $1 +$ la menor
%cantidad de saltos que requiera llegar desde cualquiera de sus 
%vecinos al objetivo. 

\section{Pseudocódigo}
Para entender el pseudocódigo necesito considerar dos cosas muy importantes:\\
\textbf{Tablero t}: que representa el tablero en el que van a estar distribuidos los caballos. Cada Tablero cuenta con $NxN$ casillas.\\
\textbf{Vector caballos}: es un vector que representa los caballos que están sobre el tablero. Cada elemento del vector $caballos$ en realidad representa a uno o más de un caballo. Si hay más de un caballo sobre una casilla inicialmente, todos esos caballos serán representados por un elemento del vector. A cada elemento del vector $caballos$ lo vamos a llamar de ahora en adelante $id\_caballos$ ya que cada elemento cuenta con un $id$ y como se dijo antes no representa a un caballo sino a todos los caballos que estén inicialmente sobre una casilla. De esta manera la cantidad de $id\_caballos$ que tenga el vector $caballos$ (longitud del vector) será la cantidad de casillas ocupadas inicialmente en el tablero.\\

Teniendo en cuenta estas dos estructuras, se puede explicar mejor el comportamiento de las 2 funciones más relevantes para el algoritmo:\\

\begin{algorithm}[H]
\KwData{Void ej2()}

	{Recibe parametros de entarada}\\
	Arma el tablero $t$\\
	Crea el vector $caballos$
		
	\ForAll {Para cada uno de los $d$ id\_caballo en vector $caballos$} {
			caminoCorto(Tablero $t$, id\_caballo $d$, ultimo id\_caballo)
	}
		
	devolverResultados

\caption{Void ej2}
\label{alg:ej2}
\end{algorithm}

Teniendo en cuenta los conjuntos $C_{k,(x,y)}$ definidos líneas atras la función $caminoCorto$ va recorriendo las casillas a partir de la casilla inicial y visitando los vecinos no visitados y asignandoles a cada casillas la $k$ (cantidad de saltos mínimos) respectiva.
Recorre el tablero una cantidad $l$ de veces, donde $l$ es la longitud del arreglo $caballos$ de manera que la primera recorrida guarda los $k$ correspondientes a cada casilla y ese resultado va acumulandose en cada iteración de manera que cuando se llega a la iteración $l$, al final de todo, cada casilla va a contener el acumulado de todos los $k$, lo cual resulta ser la sumatoria de todos los movimientos de los caballos para llegar a dicha casilla. 

\begin{algorithm}[H]
\KwData{caminoCorto(tablero $t$, idCaballo $d$, int $ultimo$)}
	variables:\\
	$x$ = d.posicionx (fila en casilla de idCaballo $d$)\\
	$y$ = d.posiciony (columna en casilla de idCaballo $d$)\\
	$id$ = d.id  (id unico de $d$)\\
	$cant$ = cantidad de caballos que representa d\;
	cola (x,y,kSaltos) $c$; (para encolar posx, posy y una cantidad de saltos $k$)\\
	encolar $c$(x,y,0)
		
	\While{cola $c$ no este vacia}{
	  a = desencolar(c)\;
	  x = a.x\;
	  y = a.y\;
	  s = a.kSaltos + 1\;
	  
	  \ForAll { Para cada (i,j) perteneciente a $Vecinos(x,y)$}{
		\If {esPosicionValida(t,i,j)}{
				\If{t[x][y].idActual != id}{
				//si el idCabalo actual no visito la casilla entonces\\
					t[x][y].acum += (cant*s)\;
					//acumulo los saltos en atributo acum de la casilla\\
					encolar c((x,y,s))\;
					\If{t[x][y].idActual != id-1}{
					// si el idCabalo anterior que visito la casilla no coincide con id-1, seguramente no llego y entonces no todos los caballos llegaron a esta casilla\\
					t[x][y].lleganTodos = false;
					}
				
				}
			}	
		
		}
	 }	
	
	
\caption{caminoCorto}
\label{alg:ej2}
\end{algorithm}





\section{Correctitud y Complejidad}

\subsection{Correctitud}

El algoritmo recorre con cada $idCaballo$ el tablero llenando los $k$ en cada casilla pertenecientes a $C_{k(S)}$ para el valor de $k$ correspondiente y para $S$ como casilla inicial a la que corresponde $idCaballo$.
Y en cada recorrido al tablero va acumulando la sumatoria de los $k$ correspondiente a cada casilla. Centremonos en el recorrido de un solo $idCaballo$ y pasaremos a demostrar porque en cada casilla que recorre el algoritmo estoy seguro de que guardará el $k$ correspondiente a esa casilla.\\

Pensemos el algoritmo de la siguiente manera:\\
Dada la siguiente función de contrucción de los conjuntos $C_{k,(S)}$ definida inductivamente como:
\begin{itemize}
\item $C_{0,(S)} = \{S\}$ conjunto de casillas a las que se llega con un mínimo de cero saltos desde S
\item  Dado un $C_{k,(S)}$ se define  $C_{k+1(S)}$ = \{ T, tal que T pertenece a $Vecinos(F)$ para algún F del conjunto $C_{k,(S)}$ y T no pertenece a ningun conjunto $C_{i,(S)}$ con $0\le i \le k$ \}
\end{itemize}
El algoritmo es un reflejo de esta definición:
\begin{itemize}
\item Llenar la casilla $S$ (casilla inicial) con el valor $K=0$ es análogo a completar el conjunto de los $C_{0,(S)}$ con $\{S\}$
\item Luego una vez llena la primer casilla se continua con sus vecinos asignandoles el valor $K=1$. Para luego seguir con las casillas vecinas a estas.
\item Una vez llenas las casillas con un número $k$, para llenar las casillas vecinas a estas, necesito comprovar que no han sido llenadas antes y esto es análogo al paso inductivo de la definición de conjuntos $C_{i,(S)}$  con $i$ un natural cualquiera. 
\end{itemize}
Entonces si demostramos que la definición de los conjuntos es correcta, estamos demostrando que el algoritmo también es correcto. Analizando la definición de los conjuntos paso a paso vemos que:

\begin{itemize}
\item el primer paso tiene que ser correcto ya que la única casilla a la que se puede llegar con 0 movimientos desde una casilla $S$ es la misma casilla S.
\item Entonces analicemos el paso inductivo, dado un conjunto $C_{k,(S)}$ que es correcto (contiene las casillas a las que se minimiza la cantidad de movimientos a $k$ para llegar) y los conjuntos anteriores también son correctos. Se define el siguiente conjunto (conjunto $k+1$) como las casillas a las que se llega con $k+1$ movimientos: como vecinos del conjunto anterior que no pertenezcan a ninguno de los conjuntos definidos anteriormente.
\item Supongamos que la construcción de los conjuntos no es correcto para el paso $k+1$ entonces suponiendo que en el conjunto $k+1$ se encuentra alguna casilla x que no es vecino de algún elemento del conjunto $k$ sino mas bien vecino de un elemento de un conjunto $n$. Si $n<k$ entonces $x$ tiene que pertenecer como mucho al conjunto $n+1$ o a alguno anterior lo cual es absurdo ya que pertenece a $k+1$. El siguiente caso es pensar que $x$ es vecino de alguna casilla del conjunto $m$ con $k+1<m$ pero esto no puede pasar ya que si $x$ no es vecino de alguna casilla de $k$ se llegaria a $x$ desde $S$ con muchas mas iteraciones y nuevamente llegamos a un absurdo ya que $x$ pertenece al conjunto $k+1$.
\item Necesariamente $x$ tiene que pertenecer a algun vecino de algun elemento del conjunto $k$ y ademas claramente no pertenece a ningun conjunto anterior sino ya que no puede llegar con k+1 salto como minimo desde S y a la vez con $n$ saltos como minimo con n menor estricto a k+1.
\item Entonces la definición de los conjuntos es correcta, lo que hace que el algoritmo sea correcto también.
\end{itemize}

 
\subsection{Complejidad}
Si $n$ es la cantidad de filas (o columnas) del tablero y $k$ la cantidad de caballos dentro del tablero, la complejidad del algoritmo se define como $T(F(n,k))$ que será la suma de las complejidades de cada función dentro del algoritmo:
$$T(f(n,m)) = T(armarTablero + armarArregloCaballos + porCadaDcaminiCorto + devResultado)$$
Analizando cada subfunción tenemos las siguientes complejidades:
$$T(construirTablero) = O(n*n)$$
construye casilla por casilla y llena en cada una los atributos correspondientes
$$T(construirArregloCaballos) = O(k)$$
cicla k veces para crear el arreglo
$$T(porCadaIdCaballo hace caminiCorto) = O(l*n*n)$$
caminoCorto tiene una complejidad de O(n*n) ya que en cada iteración del ciclo principal realiza siempre operaciones en O(1) y lo hace una cantidad constante de veces. En el pseudocódigo hay un for dentro del ciclo principal, pero ese for recorre los Vecinos de una casilla que siempre son 8 y para cada vecino se realiza una cantidad acotada de operaciones en O(1). El ciclo principal (while()) lo ejecuta (n*n) veces ya que lo hace tantas veces se encolen elementos en la cola, y en la cola solo se encolaran las casillas que no han sido vivitadas antes. En conclusión la complejidad de esta función es O(n*n). La llamada a la función caminoCorto la ejecuta l veces donde l es la cantidad de casillas ocupadas inicialmente.
$$T(devolverResultado) = O(n*n)$$
Recorre el tablero para fijarse en el valor minimo y devolver el resultado.\\
El resultado quedaría:
$$T(f(n,m)) = O( max\{(n*n), k , (l*n*n) , (n*n)\} )$$
además como $l<=k$ entonces se puede acotar a $l$ por $k$
$$T(f(n,m)) = O(k*n*n)$$
\subsection{Test de performance}
Se puede ver en el gráfico \ref{fig:ej2:complejidadn} que la complejidad, tomando en cuenta el parametro cantidad de filas y columnas, se comporta como se esperaba. Analogamente, el gráfico \ref{fig:ej2:complejidadk} muestra la linealidad del parametro cantidad de caballos con respecto al tiempo de ejecución.
\ponerGrafico{imagenes/ej2n.pdf}{Comparativa parametro n - Cantidad de filas y columnas.}{1}{ej2:complejidadn}
\ponerGrafico{imagenes/ej2k.pdf}{Comparativa parametro k - Cantidad de caballos.}{1}{ej2:complejidadk}
